#
# author: viet cuong
# date: 13/10/11
#
# Simple Apriori implementation
# 
# In this version, the transactions are stored by array. Checking contained operation
# is done by an O(n) loop
#
# Input format:
# 1 2 3 4
# 1 2
# 2 3 4
# 2 3
# 1 2 3
# 3 4
# 2 4
# 
# Output format: with min sup = 3
# 1 2
# 3 4
# 2 3
# 4
#

import os
from optparse import OptionParser
from collections import *

class SimpleApriori:

    # Init
    def __init__(self, minsup = 1):
        self.transactions = []
        self.output_data = ''
        
        self.minsup = minsup
        
    # Read transaction data
    def read_transactiondata(self, filename):
        f = open(filename, "r")
        for line in f.readlines():
            words = line[:-1].split(" ")
            if len(words) < 1: break
            new_transaction = []
            for w in words:
                if len(w) > 0:
                    new_transaction += [int(w)]
                    
            if len(new_transaction) > 0:
                self.transactions += [new_transaction]
        f.close()
        
        # DEBUG
        print self.transactions
        
    # Write to output file
    def write_to_file(self, filename):
        f = open(filename, "w")
        f.write(self.output_data)
        f.close()
        
    # Init step:
    # - Find 1-frequent-pattern
    def init_step(self):
        
        self.frequent_pattern = set()
        
        counter = Counter()
        
        # Add all pattern to the list
        for transaction in self.transactions:
            item_set = set(transaction)
            
            for item in item_set: counter[item] += 1
            
        # DEBUG
        #print counter
            
        # Only add the patterns have the support >= minsup
        for item in counter:
            if counter[item] >= self.minsup: self.frequent_pattern.add(tuple([item]))
        
        # DEBUG
        #print self.frequent_pattern
        
    # Check a pattern appear in a transaction
    def is_appear(self, pattern, transaction):
        if len(pattern) > len(transaction): return False
        
        # DEBUG
        #print pattern, transaction
        for i in range(len(transaction) - len(pattern) + 1):
            appear = True
            for j in range(len(pattern)):
                if pattern[j] != transaction[i+j]:
                    appear = False
                    break
                    
            if appear: return True
        
        return False
        
    # Find frequent pattern
    def find_frequent_pattern(self):
        
        prev_pattern = set(self.frequent_pattern)
        
        # DEBUG
        print prev_pattern
        
        while True:
            # Generate the pattern of the k step, from the k-1 step
            new_candidate_pattern = set()
            for p1 in prev_pattern:
                for p2 in prev_pattern:
                    if p1 != p2:
                        newp = list(p1)
                        newp += [p2[-1]]
                        new_candidate_pattern.add(tuple(newp))

            # DEBUG         
            #print new_candidate_pattern
            
            # Delete the new pattern if one of its subsequence does not belong to 
            # the k-1 set
            tmp = []
            for new_pattern in new_candidate_pattern:
                prun = False
                for i in range(len(new_pattern)):
                    subsequence = list(new_pattern)
                    subsequence.pop(i)
                    if tuple(subsequence) not in prev_pattern:
                        prun = True
                        break
                        
                if not prun: tmp += [(new_pattern)]
            
            # Counting the pattern in the tmp
            # to prun which has support < min sup
            new_candidate_pattern = set()
            for new_pattern in tmp:
                count = 0
                for transaction in self.transactions:
                    if self.is_appear(new_pattern, transaction):
                        count += 1
                
                # DEBUG
                #print new_pattern, count
                if count >= self.minsup:
                    new_candidate_pattern.add(new_pattern)
                    
            if len(new_candidate_pattern) == 0:
                break
                
            prev_pattern = new_candidate_pattern
            
            # DEBUG         
            print len(new_candidate_pattern)
            
    # Run the apriori algorithm
    def run(self):
        self.init_step()
        self.find_frequent_pattern()
            
# Main
if __name__=="__main__":
    parser = OptionParser()
    parser.add_option("-i", dest="input_file", default="data.in", type="string", help="transaction data", metavar="FILE")
    parser.add_option("-o", dest="output_file", default="data.out", type="string", help="mined sequential pattern", metavar="FILE")
    parser.add_option("-m", dest="minsup", default=1, type="int", help="min support value", metavar="int")
    parser.add_option("-a", dest="all", action="store_true", default = False)
    
    (options, args) = parser.parse_args()
    
    apriori = SimpleApriori(minsup = options.minsup)
    
    apriori.read_transactiondata(options.input_file)
    apriori.run()
    